2012년03월03일 5번
[과목 구분 없음] 다음 중 데이터 값의 대소를 비교하여 정렬하는 문제에 대한 가장 빠른 알고리즘의 시간 복잡도는? (단, n은 정렬 대상의 입력 데이터 수이다.)
- ① O(n)
- ② O(log2n)
- ③ O(nlog2n)
- ④ O(n2)
(정답률: 63%)
문제 해설
O(nlog2n)이 가장 빠른 알고리즘이다. 이유는 대부분의 정렬 알고리즘이 비교 기반 알고리즘이기 때문이다. 비교 기반 알고리즘은 최소 O(nlog2n)의 시간 복잡도를 가지며, 이는 정보 이론적으로 최적의 시간 복잡도이다. 따라서 O(nlog2n)이 가장 빠른 알고리즘이다.
